package com.leetcode.tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @Author zhang.xin
 * @Description: TODO(这里描述)
 * @Date 2019/12/28
 */
public class Leetcode98 {

    /**
     * 对树进行中序遍历，判断后一个结点的值一点前一个结点的值大
     * @param root 根节点
     * @return 是否二叉搜索树
     */
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (root.left == null && root.right == null)
            return true;
        double nowVal = - Double.MAX_VALUE;
        List<TreeNode> list = new LinkedList<>();
        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<>();
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.empty()) {
                TreeNode n = stack.pop();
                if (n.val <= nowVal) return false;
                nowVal = n.val;
                node = n.right;
            }
        }
        return true;
    }

    private TreeNode creatTree() {
        TreeNode t1 = new TreeNode(5);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(7);
        TreeNode t4 = new TreeNode(1);
        TreeNode t6 = new TreeNode(4);
        TreeNode t5 = new TreeNode(6);
        TreeNode t7 = new TreeNode(8);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t6;
        t3.left = t5;
        t3.right = t7;
        return t1;
    }

    public static void main(String[] args) {
        Leetcode98 leet = new Leetcode98();
        TreeNode root = leet.creatTree();
        System.out.println(leet.isValidBST(root));

    }

}
